#define _CRT_SECURE_NO_WARNINGS

#include "stdio.h"
#include "stdlib.h"

#define MAXSIZE 100

typedef int ElemType;

typedef struct {
	ElemType data;
	int cur;  //存放下一个结点的游标
}component, SLinkList[MAXSIZE];

//静态链表初始化
void InitSpace_SL(SLinkList& space) {
	for (int i = 0; i < MAXSIZE; i++) {
		space[i].cur = i + 1;
	}
	space[MAXSIZE - 1].cur = 0;
}

//创建结点
int Malloc_SL(SLinkList& space) {
	int i = space[0].cur;  //第一个空结点
	if (space[0].cur) space[0].cur = space[i].cur;  //如果备用链表非空
	return i;
}

//释放结点
void Free_SL(SLinkList& space, int k) {
	space[k].cur = space[0].cur;
	space[0].cur = k;
}

//查找节点
int LocateElem_SL(SLinkList space, ElemType e) {
	int i = space[0].cur;
	while (i && space[i].data != e) {
		i = space[i].cur;
	}
	return i;
}

//输入集合A和集合B，在space中建立集合(A-B)∪(B-A)
void difference(SLinkList& space, int& S) {
	InitSpace_SL(space);
	S = Malloc_SL(space);  //创建头结点
	int r = S;  //r指向尾结点
	int m, n;  //集合元素个数
	printf("输入集合A的个数：");
	scanf("%d", &m);
	printf("输入集合B的个数");
	scanf("%d", &n);
	printf("输入集合A：");
	//输入集合A
	for (int j = 0; j < m; j++) {
		int i = Malloc_SL(space);  //创建新节点
		scanf("%d", &space[i].data);
		//将新结点接入space的尾部
		//space[i].cur = space[r].cur;
		space[r].cur = i;
		r = i;
	}
	space[r].cur = 0;
	printf("输入集合B：");
	//输入集合B
	for (int j = 0; j < n; j++) {
		int p = S;  //p指向相同结点的后一个结点
		int k = space[S].cur;  //k指向第一个结点
		ElemType b;  //插入的元素
		scanf("%d", &b);
		while (k != space[r].cur && space[k].data != b) {  //查找是否有相同的结点
			p = k;
			k = space[k].cur;
		}
		if (k == space[r].cur) {  //如果没有找到，就往后插入结点
			int i = Malloc_SL(space);
			space[i].data = b;
			space[i].cur = space[r].cur;
			space[r].cur = i;
		}
		else {  //找到了，删除结点
			space[p].cur = space[k].cur;
			Free_SL(space,k);
			if (k == r) r = p;  //如果删除的为最后一个结点，r的指向删除的前一个结点
		}
	}
}

//头插法插入结点
void Insert_SL(SLinkList& space, ElemType e) {
	int i = Malloc_SL(space);  //创建新结点
	space[i].data = e;
	if (i == 0) {  //如果是空结点
		space[i].cur = 0;
	}
	else {
		space[i].cur = space[0].cur;
	}
	space[0].cur = i;
}

//头删
void Delete_SL(SLinkList &space) {
	int p = space[0].cur;
	space[0].cur = space[p].cur;
	Free_SL(space, p);  //释放删除结点
}

//输出静态链表
void Print_SL(SLinkList space,int S) {
	int P = space[S].cur;
	while (P) {
		printf("%3d", space[P].data);
		P = space[P].cur;
	}
	printf("\n");
}

int main() {
	SLinkList space;  //创建一个静态链表
	int S=0;  //集合(A-B)∪(B-A)的结果
	difference(space, S);
	Print_SL(space,S);
}